package org.nowcoder.leetcode.prefixSum;

import java.util.ArrayDeque;

/**
 * Title  : 1022. Sum of Root To Leaf Binary Numbers
 * Source : https://leetcode.cn/problems/sum-of-root-to-leaf-binary-numbers/description/
 * Author : XrazYang
 * Date   : 2024-05-16
 */

public class LeetCode_1022 {

    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    private int max = 0;

    public int sumRootToLeaf(TreeNode root) {
        //dfs(root, "");
        preOrder(root);
        return max;
    }


    private void preOrder(TreeNode root) {
        ArrayDeque<TreeNode> sta = new ArrayDeque<>();
        ArrayDeque<String> pathSta = new ArrayDeque<>();
        sta.push(root);
        pathSta.offer(String.valueOf(root.val));
        while (!sta.isEmpty()) {
            TreeNode node = sta.pop();
            String s = pathSta.pop();
            if (node.left == null && node.right == null) {
                max += Integer.parseInt(s, 2);
            }
            if (node.right != null) {
                sta.push(node.right);
                pathSta.push(s + node.right.val);
            }
            if (node.left != null) {
                sta.push(node.left);
                pathSta.push(s + node.left.val);
            }
        }
    }

    private void dfs(TreeNode root, String path) {
        if (root != null) {
            StringBuilder builder = new StringBuilder(path);
            builder.append(root.val);
            if (root.left == null && root.right == null) {
                max += Integer.parseInt(builder.toString(), 2);
            } else {
                dfs(root.left, builder.toString());
                dfs(root.right, builder.toString());
            }
        }
    }
}
